A finite state machine models or programs a system as a finite set of states with transitions between them. The transitions are often labelled by some sort of action or terms. Examples of the user of finie state machines include in robotic systems or software agents to respond to events, and in natural language processing to represent aspects of grammar. Based on the latter come forms of pattern matching inclusing regular expressions are complied in to finite state machines for efficient execution.
A four state finite state machine that encodes the reguar expression {(A|B|C)*}
| S0 => | # at least one A at start |
| S1 => | # anything |
| S2 => | # B followed by B or A |
| S3 => | # C followed by C or A |